// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/base/lookup_string_in_fixed_set.h"

#include <ostream>
#include <string.h>

#include "testing/gtest/include/gtest/gtest.h"

namespace net {
namespace {
    namespace test1 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest1-inc.cc"
    }
    namespace test3 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest3-inc.cc"
    }
    namespace test4 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest4-inc.cc"
    }
    namespace test5 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest5-inc.cc"
    }
    namespace test6 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest6-inc.cc"
    }

    struct Expectation {
        const char* const key;
        int value;
    };

    void PrintTo(const Expectation& expectation, std::ostream* os)
    {
        *os << "{\"" << expectation.key << "\", " << expectation.value << "}";
    }

    class LookupStringInFixedSetTest : public testing::TestWithParam<Expectation> {
    protected:
        template <size_t N>
        int LookupInGraph(const unsigned char (&graph)[N], const char* key)
        {
            return LookupStringInFixedSet(graph, N, key, strlen(key));
        }
    };

    class Dafsa1Test : public LookupStringInFixedSetTest {
    };

    TEST_P(Dafsa1Test, BasicTest)
    {
        const Expectation& param = GetParam();
        EXPECT_EQ(param.value, LookupInGraph(test1::kDafsa, param.key));
    }

    const Expectation kBasicTestCases[] = {
        { "", -1 },
        { "j", -1 },
        { "jp", 0 },
        { "jjp", -1 },
        { "jpp", -1 },
        { "bar.jp", 2 },
        { "pref.bar.jp", 1 },
        { "c", 2 },
        { "b.c", 1 },
        { "priv.no", 4 },
    };

    INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
        Dafsa1Test,
        ::testing::ValuesIn(kBasicTestCases));

    class Dafsa3Test : public LookupStringInFixedSetTest {
    };

    // This DAFSA is constructed so that labels begin and end with unique
    // characters, which makes it impossible to merge labels. Each inner node
    // is about 100 bytes and a one byte offset can at most add 64 bytes to
    // previous offset. Thus the paths must go over two byte offsets.
    TEST_P(Dafsa3Test, TestDafsaTwoByteOffsets)
    {
        const Expectation& param = GetParam();
        EXPECT_EQ(param.value, LookupInGraph(test3::kDafsa, param.key));
    }

    const Expectation kTwoByteOffsetTestCases[] = {
        { "0________________________________________________________________________"
          "____________________________0",
            0 },
        { "7________________________________________________________________________"
          "____________________________7",
            4 },
        { "a________________________________________________________________________"
          "____________________________8",
            -1 },
    };

    INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
        Dafsa3Test,
        ::testing::ValuesIn(kTwoByteOffsetTestCases));

    class Dafsa4Test : public LookupStringInFixedSetTest {
    };

    // This DAFSA is constructed so that labels begin and end with unique
    // characters, which makes it impossible to merge labels. The byte array
    // has a size of ~54k. A two byte offset can add at most add 8k to the
    // previous offset. Since we can skip only forward in memory, the nodes
    // representing the return values must be located near the end of the byte
    // array. The probability that we can reach from an arbitrary inner node to
    // a return value without using a three byte offset is small (but not zero).
    // The test is repeated with some different keys and with a reasonable
    // probability at least one of the tested paths has go over a three byte
    // offset.
    TEST_P(Dafsa4Test, TestDafsaThreeByteOffsets)
    {
        const Expectation& param = GetParam();
        EXPECT_EQ(param.value, LookupInGraph(test4::kDafsa, param.key));
    }

    const Expectation kThreeByteOffsetTestCases[] = {
        { "Z6_______________________________________________________________________"
          "_____________________________Z6",
            0 },
        { "Z7_______________________________________________________________________"
          "_____________________________Z7",
            4 },
        { "Za_______________________________________________________________________"
          "_____________________________Z8",
            -1 },
    };

    INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
        Dafsa4Test,
        ::testing::ValuesIn(kThreeByteOffsetTestCases));

    class Dafsa5Test : public LookupStringInFixedSetTest {
    };

    // This DAFSA is constructed from words with similar prefixes but distinct
    // suffixes. The DAFSA will then form a trie with the implicit source node
    // as root.
    TEST_P(Dafsa5Test, TestDafsaJoinedPrefixes)
    {
        const Expectation& param = GetParam();
        EXPECT_EQ(param.value, LookupInGraph(test5::kDafsa, param.key));
    }

    const Expectation kJoinedPrefixesTestCases[] = {
        { "ai", 0 },
        { "bj", 4 },
        { "aak", 0 },
        { "bbl", 4 },
        { "aaa", -1 },
        { "bbb", -1 },
        { "aaaam", 0 },
        { "bbbbn", 0 },
    };

    INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
        Dafsa5Test,
        ::testing::ValuesIn(kJoinedPrefixesTestCases));

    class Dafsa6Test : public LookupStringInFixedSetTest {
    };

    // This DAFSA is constructed from words with similar suffixes but distinct
    // prefixes. The DAFSA will then form a trie with the implicit sink node as
    // root.
    TEST_P(Dafsa6Test, TestDafsaJoinedSuffixes)
    {
        const Expectation& param = GetParam();
        EXPECT_EQ(param.value, LookupInGraph(test6::kDafsa, param.key));
    }

    const Expectation kJoinedSuffixesTestCases[] = {
        { "ia", 0 },
        { "jb", 4 },
        { "kaa", 0 },
        { "lbb", 4 },
        { "aaa", -1 },
        { "bbb", -1 },
        { "maaaa", 0 },
        { "nbbbb", 0 },
    };

    INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
        Dafsa6Test,
        ::testing::ValuesIn(kJoinedSuffixesTestCases));

} // namespace
} // namespace net
